package main

import (
	"fmt"
	"sort"
)

//hash表: 16ms 62%, 5.9MB 13%
func majorityElement(nums []int) int {
	m := map[int]int{}
	for _, v := range nums {
		m[v]++
		if m[v]*2 > len(nums) {
			return v
		}
	}
	return 0
}

//排序:16ms 62%, 5.9MB 99%
func majorityElement1(nums []int) int {
	sort.Ints(nums)
	return nums[len(nums)/2]
}

//摩尔投票法:12ms 92%, 5.9MB 99%
func majorityElement2(nums []int) int {
	x := nums[0]
	votes := 0
	for i, v := range nums {
		if v == x {
			votes++
		} else {
			votes--
			if votes == 0 {
				x = nums[i+1]
			}
		}
	}
	return x
}

func main() {
	fmt.Println(majorityElement([]int{1, 2, 3, 2, 2, 2, 5, 4, 2}))
	fmt.Println(majorityElement1([]int{1, 2, 3, 2, 2, 2, 5, 4, 2}))
	fmt.Println(majorityElement2([]int{1, 2, 3, 2, 2, 2, 5, 4, 2}))
}
